COMMENT ⊗   VALID 00002 PAGES
C REC  PAGE   DESCRIPTION
C00001 00001
C00002 00002	\magnification\magstephalf
C00012 ENDMK
C⊗;
\magnification\magstephalf
\input macro.tex
\def\today{\ifcase\month\or
  January\or February\or March\or April\or May\or June\or
  July\or August\or September\or October\or November\or December\fi
  \space\number\day, \number\year}
\baselineskip 14pt
\def\fnc#1{\mathop{\rm #1}\nolimits}
\rm
\line{\sevenrm a05.tex[154,phy] \today\hfill}

\bigskip
\line{\bf Unsolvability of Formal Language Problems\hfill}

\medskip
\disleft 25pt:(1):
By definition, a Turing Machine (TM) consists of a finite control, input,
output, and one memory device, a tape.

\figbox 1.3truein:

\disleft 25pt:(2):
A finite controller plus two stacks can simulate a tape, so every Turing
machine can be simulated by a two-stack automaton, which has the same
input-output relation.

\figbox 1.3truein:

\disleft 25pt:(3):
A computation of such a machine can be written on a 
multi-track tape, where one tracks lists the characters pushed and
popped on stack~1, one does the same for stack~2, etc.

$$\vbox{\tabskip=0pt\offinterlineskip\halign to 190pt{\hbox to 190pt{\hfill #\hfill}\cr
\noalign{\hrule}
\noalign{\smallskip}
input\cr
\noalign{\smallskip}
\noalign{\hrule}
\noalign{\smallskip}
output\cr
\noalign{\smallskip}
\noalign{\hrule}
\noalign{\smallskip}
control state\cr
\noalign{\smallskip}
\noalign{\hrule}
\noalign{\smallskip}
stack 1 action\cr
\noalign{\smallskip}
\noalign{\hrule}
\noalign{\smallskip}
stack 2 action\cr
\noalign{\smallskip}
\noalign{\hrule}
\cr}}$$

\bigskip
\disleft 25pt:(4):
Such a tape is a computation of the machine if it meets local
conditions implied by its finite-state control, and if each stack track
is a possible stack history. These three conditions can each be tested
by a filter; the first filter is finite-state, the other two are DPDAs
which are easily shown to filter context-free languages.

\smallskip
\disleft 25pt:(5):
So, the set of computational histories is FAL $∩$ DCFL $∩$ DCFL; since
$\hbox{FAL}∩\hbox{DCFL}$ is a DCFL, the set of computational histories
is $\hbox{DCFL}∩\hbox{DCFL}$.

\smallskip
\disleft 25pt::
If we want the set of histories that read a particular input, we get
that by intersecting with another FAL; the result is still
$\hbox{DCFL}∩\hbox{DCFL}$.

\smallskip
\disleft 25pt:(6):
The problem whether the original TM accepts any string, and the problem
whether it accepts a given particular string, is now
the problem whether two DCFLs have a non-empty intersection. If we
had a general algorithm for that problem, we would have a general
algorithm for halting problems, impossible.
Result~1: The empty intersection problem is undecidable for DCFLs,
{\sl a fortiori\/} for CFLs.

\smallskip
\disleft 25pt:(7):
Since we can readily construct unambiguous CFGs $G↓1$ and $G↓2$ for any
two DCFLs, say with roots $S↓1$ and~$S↓2$ and disjoint sets of
non-terminals, by adding productions $S→S↓1$, $S→S↓2$  we have a
grammar which is ambiguous if and only if the intersection of the
DCFLs is non-empty. So (Result~2) whether a CFG is ambiguous is
also undecidable.

\smallskip
\disleft 25pt:(8):
Since the complement of a DPDA language is also one, the complement
of a~DCFL is also one. By deMorgan's  laws,
$L↓1∩L↓2=\overline{\overline{L↓1}∪\overline{L↓2}}$. Since 
$\overline{L↓1}∪\overline{L↓2}$
for DCFLs $L↓1$ and $L↓2$ is a readily constructed CFL, the question
whether the intersection of two DCFLs is empty can be transformed
into the question whether the complement of a certain CFL is empty, i.e.,
whether that CFL is equal to $\Sigma↑{\ast}$ for some finite 
alphabet~$\Sigma$. So (Result 3) the problem whether a given CFL
includes all the strings over its alphabet is also undecidable.

\smallskip
\disleft 25pt:(9):
The above implies that (Result 4) you also can't test whether one
CFL is equal to another, or (Result~5) whether one CFL is equal to
one FAL; if it could be decided in general, it could be decided
for the special case that the second language is~$\Sigma↑{\ast}$.

\smallskip
\disleft 25pt:(10):
Given two CFLs $L↓1$ and $L↓2$, we can construct the auxiliary CFLs
$a↑ib↑ic↑{\ast}:L↓1$ and
$a↑{\ast}b↑ic↑i:L↓2$. The intersection is empty if $L↓1∩L↓2$ is empty;
if $L↓1∩L↓2$ is non-empty, we can see (by intersection with the
FAL $a↑{\ast}b↑{\ast}c↑{\ast}:x$, where $x\in L↓1∩L↓2$) that the
intersection of the auxiliary languages is not empty, not finite,
not a~FAL, and not a~CFL. So, the question whether the intersection
of two CFLs is a FAL, or whether it is a~CFL, or whether it is finite,
is also undecidable. That's Results 6, 7, and~8.

\smallskip
So, most of the general questions we might have about CFLs either are
known to be undecidable, or have simple well-understood algorithms.
In the list below, $x$'s are strings, $L$'s are CFL's, $F$'s~are FAL's,
$D$'s~are DCFL's.

\smallskip
\disleft 80pt:{Inclusion:}: $x\in F$, $x\in L$, $x\in D$ are decidable.
\display 60pt:: (CYK algorithm, etc.)

\smallskip
\disleft 80pt:{Intersection:}: $F↓1∩F↓2$ is a FAL.
\display 80pt:: $F↓1∩D↓1$ is a DCFL.
\display 80pt:: $F↓1∩L↓1$ is a CFL.
\display 60pt:: Whether $D↓1∩D↓2$, $D↓1∩L↓1$, or $L↓1∩L↓2$ is empty,
finite, a~FAL, a~DCFL, or a~CFL are all undecidable.

\smallskip
\disleft 80pt:{Union:}: $F↓1∪F↓2$ is a FAL.
\display 80pt:: $F↓1∪D↓1$ is a DCFL.
\display 60pt:: The other unions are CFLs.

\smallskip
\disleft 80pt:{Equality:}: $F↓1=F↓2$ is decidable.
\display 60pt:: The other equality questions are undecidable. We have
not shown the undecidability of $D↓1=D↓2$; the reader is invited to try.

\smallskip
\disleft 60pt:{Ambiguity:}: $F$ is readily tested for ambiguity; it is
never inherently ambiguous. $D$~is never inherently ambiguous, but there
is no algorithm for ambiguity of grammars that works on all CFGs
whose languages are deterministic (we have not shown this, but are
pretty sure it's true). Ambiguity of a CFG is undecidable. Some CFLs
are inherently ambiguous; given a~CFG, it is undecidable whether there
is an unambiguous equivalent~CFG. (Proof elsewhere.)


\bigskip
\parindent0pt
\copyright 1984 Robert W. Floyd

First draft March 7, 1984

\bye